//package Demo2;
//
///**
// * Created with IntelliJ IDEA.
// * Description:
// * User: DELL
// * Date: 2023-04-20
// * Time: 9:45
// */
//public class MySingleList {
//
//    public static class ListNode {
//        public ListNode next;
//        public int val;
//
//        // 提供构造方法
//        public ListNode(int val) {
//            this.val = val;
//        }
//    }
//
//    public ListNode head; // 头结点
//
//    public void createNode() {
//        // 手动构造节点
//        ListNode listNode1 = new ListNode(11);
//        ListNode listNode2 = new ListNode(22);
//        ListNode listNode3 = new ListNode(33);
//        ListNode listNode4 = new ListNode(44);
//        ListNode listNode5 = new ListNode(55);
//
//        // 手动构建指向
//        listNode1.next = listNode2;
//        listNode2.next = listNode3;
//        listNode3.next = listNode4;
//        listNode4.next = listNode5;
//        // 最后一个节点的 next 为空
//
//        this.head = listNode1; // 头结点初始化
//    }
//
//    // 打印节点
//    public void displayNode() {
//        ListNode cur = head;
//        while (cur != null) {
//            System.out.print(cur.val + " ");
//            cur = cur.next;
//        }
//    }
//
//    // 计算节点个数
//    public int size() {
//        int count = 0;
//        ListNode cur = head;
//        while (cur != null) {
//            count++;
//            cur = cur.next;
//        }
//        return count; // 如果链表为空,返回 0
//    }
//
//    // 判断是否存在么某个节点
//    public boolean contains(int key) {
//        ListNode cur = head;
//        while (cur != null) {
//            if (cur.val == key) {
//                return true;
//            }
//            cur = cur.next;
//        }
//        return false;
//    }
//
//    // 头插法
//    public void headAdd(int key) {
//        ListNode node = new ListNode(key);
//        if (head != null) {
//            node.next = head;
//        }
//        head = node; // 更新头结点
//    }
//
//    // 尾插法
//    public void tailAdd(int key) {
//        ListNode node = new ListNode(key);
//        ListNode cur = head;
//        if (cur == null) {
//            head = node;
//        } else {
//            while (cur.next != null) {
//                cur = cur.next;
//            }
//            // 此时 cur 为尾节点
//            cur.next = node;
//        }
//    }
//
//    // 指定位置插入节点
//    public void indexAdd(int index, int key) {
//        // 判断下标合法性
//        if (index < 0 || index > size()) {
//            throw new RuntimeException("index 位置不合法!");
//        }
//
//        // 特殊情况 如果 index = 0, 头插法
//        if (index == 0) {
//            headAdd(key);
//        } else if (index == size()) {
//            tailAdd(key);
//        } else {
//            // 走 index 步找到 cur 位置
//            ListNode cur = head;
//            ListNode node = new ListNode(key);
//            while (index - 1 != 0) {
//                cur = cur.next;
//                index--;
//            }
//            // 处理指向
//            node.next = cur.next;
//            cur.next = node;
//        }
//    }
//
//    // 删除值为 val 的指定节点
//    public void delete(int key) {
//        if (head == null) {
//            throw new RuntimeException("链表为空, 无可删除节点!");
//        }
//        // 头结点的特殊删除
//        if (head.val == key) {
//            head = head.next; // 更新头结点位置
//            return;
//        }
//        // 中间位置的删除
//        // 遍历并寻找val的前一个节点
//        ListNode cur = head;
//        while (cur.next != null) {
//            // 当 cur.next指向倒数第二个节点时, 此时cur.next.val还是不等于key
//            // 则无需判断最后一个cur.next节点了
//            if (cur.next.val == key) {
//                break;
//            }
//            cur = cur.next;
//        }
//        // 更新指向
//        // 此时cur 指向当前值为key的前一个节点
//        if (cur.next == null) {
//            System.out.println("当前链表无此节点可删除!");
//            return;
//        }
//        ListNode delNode = cur.next;
//        cur.next = delNode.next;
//    }
//
//    // 删除所有指定节点
//    public void deleteAllKey(int key) {
//        if (head == null) {
//            throw new RuntimeException("链表为空, 无法删除");
//        }
//        ListNode cur = head.next;
//        ListNode prev = head;
//
//        while (cur != null) {
//            if (cur.val == key) {
//                // 更尬指向
//                prev.next = cur.next;
//            } else {
//                prev = cur; // 删了以后的下一个也可能是要删除的 因此只有当下一个节点不为key
//                //  才可以进行 pre 的更新
//            }
//            cur = cur.next; // 向后继续找
//
//        }
//
//        // 单独删除头结点
//        if (head.val == key) {
//            head = head.next;
//        }
//    }
//
//    // 清空所有节点并回收引用对象
//    public void clear() {
//        //
//        head = null;
//    }
//
//    // 翻转节点
//    public ListNode reserve() {
//        // 空链表
//        if (head == null) {
//            return null;
//        }
//
//        // 只有一个节点
//        if (head.next == null) {
//            return head;
//        }
//
//        // 两个及以上节点 -- 全部头插法后输出则为翻转结果
//        ListNode cur = head.next;
//        head.next = null;
//        while (cur != null) {
//            ListNode curNext = cur.next;
//            cur.next = head; //
//            head = cur;
//            cur = curNext;
//        }
//        return head;
//    }
//
//    // 寻找中间的节点 如果中间有两个节点 比如六个 中间就是 3 4 节点 则返回4 节点
//    public ListNode midNode() {
//        ListNode fast = head;
//        ListNode slow = head;
//
//        // fast != null 为偶数个节点时条件
//        // fast.next != null 为奇数个接地那时条件
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        return slow;
//    }
//
//    // 寻找倒数第 K 个节点
//    public ListNode indexNode(int index) {
//        ListNode fast = head;
//        ListNode slow = head;
//        if (head == null) {
//            throw new RuntimeException("当前链表为空, 无法查找!");
//        }
//        // 判断 index 合法性
//        if (index <= 0) {
//            throw new RuntimeException("index 位置不合法");
//        }
//        // 先让 fast 先走 k-index 步
//        while (index - 1 != 0) {
//            fast = fast.next;
//            if (fast == null) {
//                // 说明此时 fast 已经超过了链表长度 肯定查询不到了
//                throw new RuntimeException("index 位置不合法!");
//            }
//            index--;
//        }
//        while (fast != null) {
//
//            fast = fast.next;
//            slow = slow.next;
//
//        }
//        return slow;
//    }
//}
